package com.leetcode.algorithm.y22.m09.w1;

/**
 * 134. 加油站
 * 
 * https://leetcode.cn/problems/gas-station/
 * 
 * @author jie.deng
 *
 */
class Question0134Solution03 {

	public int canCompleteCircuit(int[] gas, int[] cost) {
		// 局部最优：当前累加rest[j]的和curSum一旦小于0，起始位置至少要是j+1
		// 全局最优：找到可以跑一圈的起始位置
		int len = gas.length;
		// 从起点出发，油箱最后剩余的油量
		int totalSum = 0;
		int curSum = 0;
		int startIdx = 0;
		for (int i = 0; i < len; i++) {
			curSum += (gas[i] - cost[i]);
			totalSum += (gas[i] - cost[i]);
			if (curSum < 0) {
				// [0,i]不能作为起点
				startIdx = i + 1;
				curSum = 0;
			}
		}
		return startIdx < len && totalSum >= 0 ? startIdx : -1;
	}

}